#include <bits/stdc++.h>
using namespace std;
using ll = long long;

char str[1000005];
int sa[1000005];
int rk[1000005];
int nrk[1000005];

int cnt[1000005];
int idk[1000005];

// 后缀排序

void suffix_sort(int n)
{
    for (int i = 1; i <= n; i++)
    {
        rk[i] = str[i];
        sa[i] = i;
    }

    for (int w = 1; w <= n; w <<= 1)
    {
        // sort(sa + 1, sa + 1 + n, [&](int a, int b)
        //      {
        //     if(rk[a] == rk[b]) return rk[a + w] < rk[b + w];
        //     return rk[a] < rk[b]; });

        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            cnt[rk[sa[i] + w]]++;
        for (int i = 1; i <= 1000000; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            idk[cnt[rk[sa[i] + w]]--] = sa[i];
        memcpy(sa, idk, sizeof(sa));

        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            cnt[rk[sa[i]]]++;
        for (int i = 1; i <= 1000000; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            idk[cnt[rk[sa[i]]]--] = sa[i];
        memcpy(sa, idk, sizeof(sa));

        for (int i = 1, p = 0; i <= n; i++)
        {
            if (rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + w] == rk[sa[i - 1] + w])
            {
                nrk[sa[i]] = p;
            }
            else
            {
                nrk[sa[i]] = ++p;
            }
        }
        memcpy(rk, nrk, sizeof(rk));
    }
}